// 前缀树，存储的是由数个小写英文字母组成的字符串路径
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

class TrieNode
{
public:
    int pass;
    int end;
    vector<TrieNode *> nexts = {nullptr};
    TrieNode()
    {
        pass = 0;
        end = 0;
        nexts.resize(26);
    }
};

class Trie
{
public:
    Trie() {}
    // 插入一个字符串的路径
    bool insert(std::string word)
    {
        char cArr[1024] = {0};
        sprintf(cArr, word.c_str(), word.size());
        // 根节点的pass++
        TrieNode *node = &root;
        node->pass++;
        // 表示字母的下标索引，例如a就是0，z就是25
        int index;
        // 计算字符索引，并将其pass++
        for (int i = 0; i < word.size(); i++)
        {
            // 小写字母的ascii码-a的ascii码
            index = cArr[i] - 'a';
            if (node->nexts[index] == nullptr)
            {
                node->nexts[index] = new TrieNode();
            }
            node = node->nexts[index];
            node->pass++;
        }
        // 最后一个字符所代表的节点的end++
        node->end++;
        return true;
    }
    // 查找一个字符串的路径在前缀树中插入了几次
    int search(string word)
    {
        char cArr[1024] = {0};
        sprintf(cArr, word.c_str(), word.size());
        TrieNode *node = &root;
        int index = -1;
        for (int i = 0; i < word.size(); i++)
        {
            index = cArr[i] - 'a';
            if (node->nexts[index] == nullptr)
            {
                return 0;
            }
            node = node->nexts[index];
        }
        return node->end;
    }
    int prefixNumber(string pre)
    {
        if (pre.empty())
        {
            return 0;
        }
        char cArr[1024] = {0};
        strcpy(cArr, pre.c_str());
        TrieNode *node = &root;
        int index = -1;
        for (int i = 0; i < pre.size(); i++)
        {
            index = cArr[i] - 'a';
            if (node->nexts[index] == nullptr)
            {
                return 0;
            }
            node = node->nexts[index];
        }
        return node->pass;
    }
    void Delete(string word)
    {
        if (search(word) != 0)
        {
            char cArr[1024] = {0};
            sprintf(cArr, word.c_str(), word.size());
            TrieNode *node = &root;
            node->pass--;
            int index = -1;
            for (int i = 0; i < word.size(); i++)
            {
                index = cArr[i] - 'a';
                // 如果当前节点的pass值为0时，word中当前字母及其下面的路径就都无效了，需要释放
                if (--node->nexts[index]->pass == 0)
                { 
                    //cpp中，这种嵌套容器的结构，需要递归到最底层，向上析构。
                    _deleteNextNode(word,node->nexts[index],i+1);
                    delete node->nexts[index];
                    node->nexts[index] = nullptr;
                    cout<<root.nexts.size()<<endl;
                    return;
                }
                node = node->nexts[index];
            }
            node->end--;
        }
    }
    /*递归析构当前节点下的有效的节点，
    word是要删除的字符串
    node表示此次要析构的节点属于哪个节点(前一个字符所对应的node)
    pos表示此次析构的字符在字符串word中的下标*/
    void _deleteNextNode(const string& word,TrieNode* node,int pos){
        if(pos==word.size()){
            return;
        }
        int index = word[pos]-'a';
        _deleteNextNode(word,node->nexts[index],pos+1);
        delete node->nexts[index];
        node->nexts[index] = nullptr;

    }

private:
    TrieNode root;
};
int main()
{
    Trie trie;
    trie.insert("abcd");

    trie.Delete("abcd");

    return 0;
}
